/*
 * @Author: szx
 * @Date: 2022-05-16 13:10:18
 * @LastEditTime: 2022-05-16 13:42:55
 * @Description:
 * @FilePath: \leetcode\面试题\04\06\06.js
 */
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function (root, p) {
    let res = null,
        prev;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        if (prev) {
            prev = null;
            res = root;
            return;
        }
        if (p.val == root.val) prev = p;
        dfs(root.right);
    };
    dfs(root);
    return res;
};
var inorderSuccessor = function (root, p) {
    const st = [];
    let prev = false;
    while (st.length || root) {
        while (root) {
            st.push(root);
            root = root.left;
        }
        const node = st.pop();
        if (prev) return node;
        if (node.val === p.val) prev = true;
        root = node.right;
    }
    return null;
};

var inorderSuccessor = function (root, p) {
    const target = p.val;
    let cur = root,
        res = null;
    while (cur) {
        if (cur.val > target) {
            res = cur;
            cur = cur.left;
        } else cur = cur.right;
    }
    return res;
};
